package datastructure.array;

/**
 *
 * @author Lei
 */
public class FindLongestIncreasingSequence {

    public static int findLongestIncreasingSequence(int[] A) {

        int[] maxEnd = new int[A.length];
        maxEnd[0] = 1;
        for (int i = 1; i < A.length; i++) {

            int maxLength = 0;
            for (int j = 0; j < i; j++) {
                if (maxEnd[j] > maxLength && A[j] < A[i]) {
                    maxLength = maxEnd[j];
                }
            }
            maxEnd[i] = maxLength + 1;
        }

        int maxi = 0;
        for (int i = 0; i < maxEnd.length; i++) {
            if (maxEnd[i] > maxi) {
                maxi = maxEnd[i];
            }
            System.out.println(maxEnd[i]);
        }
        return (maxi);
    }

    public static void main(String args[]) {
        int[] anArray = {
            0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
        };

        int length = FindLongestIncreasingSequence.findLongestIncreasingSequence(anArray);

        System.out.println("the longest length is : " + length);

    }
}
